/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/portal
   @Language: C++
   @Datetime: 19-06-25 10:22
   */

class Solution {
public:
	/**
	 * @param Maze: 
	 * @return: nothing
	 */
	int Portal(vector<vector<char> > &maze) {
		// 
		int row=maze.size(), col=maze[0].size();
		queue<long> q;
		for(int i=0; i<row && q.size()==0; ++i)
			for(int j=0; j<col && q.size()==0; ++j)
				if(maze[i][j]=='S') q.push(((i+0L)<<32)|j);
		unordered_set<long> visit;
		for(int cost=0; q.size(); ++cost){
			for(int size=q.size(); size--; q.pop()){
				const int i=q.front()>>32, j=q.front()&0xFFFFFFFF;
				if(i<0 || i>=row || j<0 || j>=col) continue;
				if(visit.count(q.front())) continue;
				visit.insert(q.front());
				if(maze[i][j]=='#') continue;
				if(maze[i][j]=='E') return cost;
				q.push(((i+1L)<<32)|j);
				q.push(((i-1L)<<32)|j);
				q.push(((i+0L)<<32)|(j+1));
				q.push(((i+0L)<<32)|(j-1));
			}
		}
		return -1;
	}
};
